package algorithm.middle;

import pojo.TreeNode;

import java.util.Arrays;

public class TrimBST669 {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        fun(root, low, high);
        return root;
    }


    public TreeNode fun(TreeNode node, int low, int high) {
        if (node == null) {
            return null;
        }
        if (node.val < low) {
            return fun(node.right, low, high);
        }
        if (node.val > high) {
            return fun(node.left, low, high);
        }
        //左
        while (node.left != null && node.left.val < low) {
            node.left = node.left.right;
        }
        //右
        while (node.right != null && node.right.val > high) {
            node.right = node.right.left;
        }
        fun(node.left, low, high);
        fun(node.right, low, high);
        return node;
    }

    public TreeNode trimBST2(TreeNode root, int low, int high) {
        if (root == null) return null;
        if (root.val < low) {
            return trimBST(root.right, low, high);
        } else if (root.val > high) {
            return trimBST(root.left, low, high);
        } else {
            root.left = trimBST(root.left, low, high);
            root.right = trimBST(root.right, low, high);
        }
        return root;
    }

}
